/**
 * 
 */
package backtrack.passed2;

import java.util.ArrayList;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class Combination {

    /**
    Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

    For example,
    If n = 4 and k = 2, a solution is:

    [
    [2,4],
    [3,4],
    [2,3],
    [1,2],
    [1,3],
    [1,4],
    ]
     */
    public List<List<Integer>> combineR0(int n, int k) {
        List<List<Integer>> combinations = new ArrayList<List<Integer>>();
        List<Integer> cache = new ArrayList<Integer>();
        combineR0Helper(n, k, 1, cache, combinations);
        return combinations;
    }
    // stack depth k
    private void combineR0Helper(int n, int k, int level, List<Integer> cache, List<List<Integer>> combinations) {
        if (cache.size() == k) {
            combinations.add(new ArrayList<>(cache));
        }
        else {
            for (int i = level; i <= n; i++) {
                cache.add(i);
                combineR0Helper(n, k, i + 1, cache, combinations);
                cache.remove(cache.size() - 1);
            }
        }
    }

    public ArrayList<ArrayList<Integer>> combineR1(int n, int k) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> buffer = new ArrayList<Integer>();
        combineR1Helper(n, k, 1, list, buffer);
        return list;
    }

 // stack depth n
    public void combineR1Helper(int n, int k, int index,
            ArrayList<ArrayList<Integer>> list, ArrayList<Integer> buffer) {
        if (index == n + 1) {
            if (buffer.size() == k) {
                list.add(new ArrayList<Integer>(buffer));
            }
        } else {
            buffer.add(index);
            combineR1Helper(n, k, index + 1, list, buffer);
            buffer.remove(buffer.size() - 1);
            combineR1Helper(n, k, index + 1, list, buffer);
        }
    }

    public ArrayList<ArrayList<Integer>> combineItr(int n, int k) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (k == 0)
            return result;
        ArrayList<Integer> buffer = new ArrayList<Integer>(k);
        ArrayList<Integer> goal = new ArrayList<Integer>(k);
        for (int i = 0; i < k; i++) {
            buffer.add(i + 1);
            goal.add(n - (k - 1) + i);
        }
        while (true) {
            result.add(new ArrayList<Integer>(buffer));
            int checker = k - 1;
            while (checker >= 0 && buffer.get(checker) == goal.get(checker))
                checker--;

            if (checker < 0)
                break;
            buffer.set(checker, buffer.get(checker) + 1);

            for (int i = checker + 1; i < k; i++)
                buffer.set(i, buffer.get(i - 1) + 1);
        }

        return result;
    }

    /**
     * 
     */
    public Combination() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        Combination comb = new Combination();
        int n = 5, k = 3;
        ArrayList<ArrayList<Integer>> list = comb.combineItr(n, k);
        comb.print(list);
    }

    public void print(ArrayList<ArrayList<Integer>> list) {
        for (ArrayList<Integer> arr : list) {
            for (Integer i : arr) {
                System.out.printf("%d,", i);
            }
            System.out.println();
        }
    }

}
